Link-Cut-Tree 的懒标记下传正确食用方法。
1:+ u v c
:将u到v的路径上的点的权值都加上自然数c;
解决方法:
很显然,我们可以split(u,v)来提取
u,v
这一段区间,提取完了将Splay(v),然后直接在v
上打加法标记add即可。- 代码:
1 | inline void pushadd(ll x,ll val){//打标记 |
2:- u1 v1 u2 v2
:将树中原有的边(u1,v1)删除,加入一条新边(u2,v2),保证操作完之后仍然是一棵树;
- 解决方法:
删除边即cut操作,加边即link操作。
代码:
1 | inline void link(ll x,ll y){ |
3:* u v c
:将u到v的路径上的点的权值都乘上自然数c;
- 解决方法:
很显然,我们可以split(u,v)来提取
u,v
这一段区间,提取完了将Splay(v),然后直接在v
上打乘法标记mul即可。(跟第一个操作基本同理)代码:
1 | inline void pushmul(ll x,ll val){//打标记 |
4:/ u v
:询问u到v的路径上的点的权值和,求出答案对于51061
的余数。
- 解决方法:
Splay(v)时已经将所有节点更新过了(懒标记下传过了),所以最后只需输出s[v]即可。
代码:
1 | //(main函数中): |
Code:
1 |
|
因为51061∗51061是会越过int界限的,所以我开的longlong(当然也可以开无符号int)
所以就没了。。。。。。
本文标题:【题解】 [国家集训队]Tree LCT luogu1501/bzoj2631
文章作者:Qiuly
发布时间:2019年02月17日 - 00:00
最后更新:2019年05月06日 - 14:04
原始链接:http://qiulyblog.github.io/2019/02/17/[题解]luoguP1501/
许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。
v1.5.2